package my.study.java.basic.algorithm.sorts;

import java.util.Random;

/**
 * 快速排序是在实践中最快的已知排序算法，方法类似于归并排序，在分割数组时选择了一个中值
 * 快速排序通常用于排序的最佳的使用选择，其期望运行时间为：O(nlgn)，能够进行就地排序。
 * 最坏运行时间为：O(n^2)
 * 算法描述：
 * 分解（divide）：数组A[beg…end]被划分为两个子数组A[beg…mid - 1]和A[mid + 1…end]，
 * 					使得A[beg…mid - 1]中的数据都小于A[mid]，A[mid + 1…end]中的数据都大于A[mid]
 * 解决（conquer）：递归地调用QuickSort
 * 合并（combine）：因为QuickSort是就地排序的，所以不需要合并操作
 * 
 * @author fanhongjie
 * 
 */
public class QuickSort {
	private static final int N = 10;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Element array[] = new Element[N];
		//int a[] = {14,6,14,14,17,8,8,14,7,16};
		Random random = new Random();
		for (int i = 0; i < N; i++) {
			array[i] = new Element(random.nextInt(2 * N));
			//array[i] = new Element(a[i]);
		}
		System.out.print("Init:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + ",");
		}
		System.out.println();
		QuickSort(array, 0, N - 1);
		System.out.print("Result:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}

	}
	private static void QuickSort(Element []array, final int start, final int end) {
		if (start == end) {
			return ;
		} else if (start + 1 == end) {
			if (array[start].compareTo(array[end]) > 0) {
				swap(array, start, end);
			}
			return;
		} else {
			int mid = Partition(array, start, end);
			QuickSort(array, start, mid - 1);
			QuickSort(array, mid + 1, end);
		}
	}
	
	private static int Partition(Element []array, final int start, final int end) {
		Median(array, start, end);
		swap(array, (start + end) / 2, end-1);
		int left = start + 1;
		int right = end - 1;
		while (left != right) {
			while (array[left].compareTo(array[end]) <= 0 && left < right) {
				left++;
			}
			while (array[right].compareTo(array[end]) > 0 && right > left) {
				right--;
			}
			swap(array, left, right);
		}
		swap(array, left, end);
		return left;
	}
	//����λ���Ƶ��������һλ������������Ƶ�����ڶ�λ
	private static void Median(Element []array, final int start, final int end) {
		int mid = (start + end) / 2; 
		if (array[start].compareTo(array[mid]) > 0) {
			swap(array, start, mid);
		}
		if (array[start].compareTo(array[end]) > 0) {
			swap(array, start, end);
		}
		if (array[mid].compareTo(array[end]) < 0) {
			swap(array, mid, end);
		}
		//return mid;
	}
	private static void swap(Element []array, int e1, int e2) {
		Element elem = array[e1];
		array[e1] = array[e2];
		array[e2] = elem;
	}

}
